﻿//1.找到快慢指针相遇的地方并返回，如果无环就返回NULL
//bool hasCycle(struct ListNode* head) {
//    //快慢指针看是否会相遇，但最好快指针一次走两步，慢指针一次走一步，就不会出现有环却不相遇的情况
//    struct ListNode* fast = head, * slow = head;
//    if (head == NULL) return false;
//    while (fast && fast->next) {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow) {
//            return true;
//        }
//    }
//    return false;
//}

////2.找环节点
//struct ListNode* detectCycle(struct ListNode* head) {
//    //这题要做出就一定要推出一个定理：两个快慢指针他们相交于环内一位置，而一指针从该位置开始走，同时另一从链表的头结点开始走，它们最终会第一次相交于环开始的那个节点。
//    // (怎么得到这个定理的一定要掌握，因为HR问到会问这个)
//    struct ListNode* fast = head, * slow = head;
//    if (head == NULL) return NULL;
//    while (fast && fast->next) {
//        //先走，防止因为头指针相等
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow) {
//            struct ListNode* ptr = head;
//            while (ptr != slow) {
//                ptr = ptr->next;
//                slow = slow->next;
//            }
//            return ptr;
//        }
//    }
//    return NULL;
//}

//上述解法的思路与算法
//
//我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
//
//如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a + n(b + c) + b = a + (n + 1)b + nc。
//
//
//
//根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有
//
//a + (n + 1)b + nc = 2(a + b)⟹a = c + (n−1)(b + c)
//有了 a = c + (n−1)(b + c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。
//
//因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。



//还有一种思路：找到相交的点后，把相交的点next指针指向空，这样就转变成了找交点问题。
